<?php
/** 
 * 
 *
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: Collections.php 14 2006-11-28 22:05:19Z rdff3 $
 */
/**
 * 
 */
require_once( "lang/Object.php" );
require_once( "util/List.php" );
require_once( "util/Collection.php" );
require_once( "util/Comparator.php" );
require_once( "util/RandomAccess.php" );
/**
 * Class Collections
 *
 * This class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that 
 * operate on collections, "wrappers", which return a new collection backed by a specified collection, and a few other odds and ends.
 * 
 * The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null.
 * 
 * The documentation for the polymorphic algorithms contained in this class generally includes a brief description of the implementation. 
 * Such descriptions should be regarded as implementation notes, rather than parts of the specification. Implementors should feel free to 
 * substitute other algorithms, so long as the specification itself is adhered to. (For example, the algorithm used by sort does not have 
 * to be a mergesort, but it does have to be stable.)
 *
 * The "destructive" algorithms contained in this class, that is, the algorithms that modify the collection on which they operate, are specified 
 * to throw UnsupportedOperationException if the collection does not support the appropriate mutation primitive(s), such as the set method. These 
 * algorithms may, but are not required to, throw this exception if an invocation would have no effect on the collection. For example, invoking 
 * the sort method on an unmodifiable list that is already sorted may or may not throw UnsupportedOperationException.
 * 
 * This class is a member of the PHP Collections Framework. 
 * 
 * @package api
 * @subpackage collections
 * @author $Author$
 * @version $Id: Collections.php 14 2006-11-28 22:05:19Z rdff3 $
 */
class Collections extends Object {


	public function __construct() {
		throw new UnsupportedOperationException();
	}

	// ============================ Public Methods  =============================================================


	static public function naturalSort( Llist $list ) {
		return self::mergeSort( $list );
	}
	static public function specificSort( Llist $list, Comparator $comparator) {
		return self::mergeSort( $list, $comparator );
	}
	
	static public function binarySearch( Llist $list, Object $key, Comparator $comparator = null ) {
		if ($list instanceof RandomAccess) 
			return self::indexBinarySearch( $list, $key, $comparator );
		else	
			return self::iteratorBinarySearch( $list, $key, $comparator );
	}
	
	static public function reverse( Llist $list ) {
		$size = $list->size();
		if ($list instanceof RandomAccess) {
			for ($i = 0, $mid = (int) $size / 2, $j = $size - 1; $i < $mid; $i++, $j--) 
				self::swap( $list, $i, $j );
		} else {
			$fwd = $list->listIterator();
			$rev = $list->listIteratorAt( $size );
			
			for ($i = 0, $mid = (int) $size / 2; $i < $mid; $i++ ) {
				$tmp = $fwd->getNext();
				$fwd->set( $rev->getPrevious() );
				$rev->set( $tmp );
			}
		}
	}
	
	static public function shuffle( Llist $list ) {
		$size = $list->size();
		if ($list instanceof RandomAccess) {
			for ($i = $size; $i > 1; $i--) 
				self::swap( $list, $i - 1, rand(0, size - 1));
		} else {
			$arr = $list->toArray();
			
			for ($i = $size; $i > 1; $i--)
				self::swapA( $arr, $i-1, rand(0, size - 1));
				
			$it = $list->listIterator();
			for ($i = 0; $i < $size; $i++) {
				$it->getNext();
				$it->set( $arr[$i] );
			}
		}
		
	}
	
	static public function swap( Llist $list, $i, $j ) {
		$list->set($i, $list->set( $j, $list->get($i)));
	}
	static public function swapA( $arr, $i, $j ) {
		$tmp = $arr[$i];
		$arr[$i] = $arr[$j];
		$arr[$j] = $tmp;
	}
	
	static public function fill( Llist $list, Object $obj ) {
		$size = $list->size();
		
		if ($list instanceof RandomAccess) {
			for ($i = 0; $i < $size; $i++) 
				$list->set( $i, $obj );
		} else {
			$itr = $list->listIterator();
			for ($i = 0; $i < $size; $i++) {
				$itr->getNext();
				$itr->set( $obj );
			}
		}
	}
	
	static public function copy( Llist $dest, Llist $src ) {
		$srcSize = $src->size();
		
		if ($srcSize < $dest->size())
			throw new IndexOutOfBoundsException("Source does not fit in destination");
			
		if ($src instanceof RandomAccess and $dest instanceof RandomAccess) {
			for ($i = 0; $i < $srcSize; $i++) 
				$dest->set($i, $src->get($i));
		} else {
			$di = $dest->listIterator();
			$si = $src->listIterator();
			for ($i = 0; $i < $srcSize; $i++) {
				$di->getNext();
				$di->set( $si->getNext() );
			}
		}
	}
	
	static public function min( Collection $c, Comparator $comparator = null ) {
		$i = $coll->iterator();
		$canidate = $i->getNext();
		
		while ($i->hasNext()) {
			$next = $i->getNext();
			if (self::cmp( $next, $canidate, $comparator) < 0)
				$canidate = $next;
		}
		return $canidate;
	}
	
	static public function max( Collection $c, Comparator $comparator = null ) {
		$i = $coll->iterator();
		$canidate = $i->getNext();
		
		while ($i->hasNext()) {
			$next = $i->getNext();
			if (self::cmp( $next, $canidate, $comparator) > 0)
				$canidate = $next;
		}
		return $canidate;
	}
	
	static public function rotate( Llist $list, $distance ) {
		if ($list instanceof RandomAccess) 
			return self::rotate1( $list, $distance );
		else
			return self::rotate2( $list, $distance );
	}
	
	static public function replaceAll( Llist $list, Object $oldVal, Object $newVal ) {
		$result = false;
		$size = $list->size();
		
		if ($list instanceof RandomAccess) {
			if ( is_null($oldVal) ) {
				for ($i = 0; $i < $size; $i++) {
					if (is_null($list->get(i))) {
						$list->set($i, $newVal);
						$result = true;
					}
				}
			} else {
				for ($i = 0; $i < $size; $i++) {
					if ($oldVal->equals( $list->get($i) )) {
						$list->set( $i, $newVal);
						$result = true;
					}
				}
			}
		} else {
			$itr = $list->listIterator();
			if (is_null( $oldVal)) {
				for ($i = 0; $i < $size; $i++) {
					if (is_null($itr->getNext())) {
						$itr->set( $newVal );
						$result = true;
					}
				}
			} else {
				for ($i = 0; $i < $size; $i++ ) {
					if ($oldVal->equals( $itr->getNext() )) {
						$itr->set($newVal);
						$result = true;
					}
				}
			}
		
		}
		return $result;
	}
	
	static public function indexOfSubList( Llist $source, Llist $target ) {
		$sourceSize = $source->size();
		$targetSize = $target->size();
		$maxCanidate = $sourceSize - $targetSize;
		
		if ($source instanceof RandomAccess and $target instanceof RandomAccess) {
			//nextCand:
				for ($canidate = 0; $canidate <= $maxCanidate; $canidate++) {
					for ($i = 0, $j = $canidate; $i < $targetSize; $i++, $j++) 
						if (! self::eq( $target->get($i), $source->get($j)))
							continue 2;
					return $canidate;
				}
		} else {
			$si = $source->listIterator();
			//nextCand:
				for ($canidate = 0; $canidate <= $maxCanidate; $canidate++) {
					$ti = $target->listIterator();
					for ($i = 0; $i < $targetSize; $i++) {
						if (! self::eq( $ti->getNext(), $si->getNext() )) {
							for ($j = 0; $j < $i; $j++)
								$si->getPrevious;
							continue 2;
						}
					}
					return $canidate;
				}
		}
		return -1;
	}
	
	static public function lastIndexOfSubList( Llist $source, Llist $target ) {
		$sourceSize = $source->size();
		$targetSize = $target->size();
		$maxCanidate = $sourceSize - $targetSize;
		
		if ($source instanceof RandomAccess and $target instanceof RandomAccess) {
			//nextCand:
				for ($canidate = $maxCanidate; $canidate >= 0; $canidate--) {
					for ($i = 0, $j = $canidate; $i < $targetSize; $i++, $j++) 
						if (! self::eq( $target->get($i), $source->get($j)))
							continue 2;
					return $canidate;
				}
		} else {
			if ($maxCanidate < 0)
				return -1;
			$si = $source->listIterator();
			//nextCand:
				for ($canidate = $maxCanidate; $canidate >= 0; $canidate--) {
					$ti = $target->listIterator();
					for ($i = 0; $i < $targetSize; $i++) {
						if (! self::eq( $ti->getNext(), $si->getNext() )) {
							if ($canidate != 0) {
								for ($j = 0; $j < $i; $j++)
									$si->getPrevious;
							}
							continue 2;
						}
					}
					return $canidate;
				}
		}
		return -1;
	}
	
	static public function unmodifiableCollection( Collection $c ) {
		return new UnmodifiableCollection( $c );
	}
	
	static public function unmodifiableSet( Set $s ) {
		return new UnmodifiableSet( $s );
	}
	
	static public function unmodifiableSortedSet( SortedSet $s ) {
		return new UnmodifiableSortedSet( $s );
	}
	
	static public function unmodifiableList( Llist $list ) {
		if ($list instanceof RandomAccess)
			return new UnmodifiableRandomAccessList( $list );
		else 
			return new UnmodifiableList( $list );
	}
	
	static public function unmodifiableMap( Map $m ) {
		return new UnmodifiableMap( $m );
	}
	
	static public function unmodifiableSortedMap( SortedMap $m ) {
		return new UnmodifiableSortedMap( $m );
	}
	
	static public function emptySet() {
		return new EmptySet();
	}
	
	static public function emptyList() {
		return new EmptyList();
	}
	
	static public function emptyMap() {
		return new EmptyMap();
	}
	
	static public function singleton( Object $o ) {
	
	}
	
	static public function singletonList( Object $o ) {
	
	}
	
	static public function singletonMap( Object $key, Object $value ) {
	
	}
	
	static public function nCopies( $n, Object $o ) {
	
	}
	
	static public function reverseOrder( Comparator $cmp = null) {
	
	}
	
	static public function frequency( Collection $c, Object $o ) {
	
	}
	
	static public function disjoint( Collection $c1, Collection $c2 ) {
	
	}
	
	static public function addAll( Collection $c, $new_elements ) {
	
	}
	
	static public function eq( Object $o1, Object $o2) {
		return (is_null($o1) ? is_null($o2) : $o1->equals( $o2 ));
	}
	
	// =============================== Private Methods ==========================================================
	
	static private function mergeSort( Llist $list, Comparator $comparator ) {
		$list_size = $list->size();
		
		if ($list_size <= 1)
			return $list;
		else {
			$middle = round($list_size / 2);
			
			$left = $list->subList(0, $middle);
			$right = $list->subList($middle, $list_size);
			
			$left = self::mergeSort( $left, $comparator );
			$right = self::mergeSort( $right, $comparator );
			
			return self::merge($left, $right, $comparator);
		}
	}
	
	
	static private function merge( Llist $left, Llist $right, Comparator $comparator ) {		
		$list_class = $left->getClass();
		$result = new $list_class();
		
		$left_size = $left->size();
		$right_size = $right->size();
		
		while ($left_size > 0 and $right_size > 0) {
			$first_left = $left->get(0);
			$first_right = $right->get(0);
			
			if ( self::cmp( $first_left, $first_right, $comparator) < 0) {
				$result->add( $first_left );
				$left = $left->subList( 1, $left_size );
				$left_size = $left->size();
			}
			else {
				$result->add( $first_right );
				$right = $right->subList( 1, $right_size );
				$right_size = $right->size();
			}
		}
		if ($left_size > 0) {
			$result->addAll( $left );
		}
		if ($right_size > 0) {
			$result->addAll( $right );
		}
		
		return $result;
	}
	
	static private function cmp( Object $o1, Object $o2, Comparator $comparator ) {
		if ( $comparator == null)
			return $o1->compareTo( $o2 );
		else
			return $comparator->compare( $o1, $o2 );
	}
	
	static private function indexedBinarySearch( Llist $list, Object $key, Comparator $comparator = null ) {
		$low = 0;
		$high = $list->size() - 1;
		
		while ($low <= $high) {
			$mid = (int) (($low + $high) / 2);
			$midVal = $list->get($mid);
			$cmp = self::cmp( $midVal, $key, $comparator );
			
			if ($cmp < 0)
				$low = $mid + 1;
			else if ($cmp > 0)
				$hight = $mid - 1;
			else 
				return mid;
		}
		return -1;
	}
	
	static private function iteratorBinarySearch( Llist $list, Object $key, Comparator $comparator = null ) {
		$low = 0;
		$high = $list->size() - 1;
		$i = $list->listIterator();
		
		while ($low <= $high) {
			$mid = (int) (($low + $high) / 2);
			$midVal = self::get($i, $mid);
			$cmp = self::cmp( $midVal, $key, $comparator );
			
			if ($cmp < 0)
				$low = $mid + 1;
			else if ($cmp > 0)
				$hight = $mid - 1;
			else 
				return mid;
		}
		return -1;
	}
	
	static private function get($i, $index ) {
		$obj = null;
		$pos = $i->nextIndex();
		if ($pos <= $index) {
			do {
				$obj = $i->getNext();
			} while ($pos++ < $index);
		} else {
			do {
				$obj = $i->getPrevious();
			} while (--$pos > $index);
		}
		return $obj;
	}
	
	static private function rotate1( Llist $list, $distance) {
		$size = $list->size();
		if ($size == 0)
			return;
		$distance = $distance % $size;
		if ($distance < 0)
			$distance += $size;
		if ($distance == 0)
			return;
			
		for ($cycleStart = 0, $nMoved = 0; $nMoved != $size; $cycleStart++ ) {
			$displaced = $list->get( $cycleStart );
			$i = $cycleStart;
			do {
				$i += $distance;
				if ($i >= $size)
					$i -= $size;
				$displaced = $list->set($i, $displaced);
				$nMoved++;
			} while($i != $cycleStart);
		}
	}
	
	static private function rotate2( Llist $list, $distance ) {
		$size = $list->size();
		if ($size == 0)
			return;
		$mid = -$distance % $size;
		if ($mid < 0)	
			$mid += $size;
		if ($mid == 0)
			return;
			
		self::reverse( $list->subList(0, $mid));
		self::reverse( $list->subList($mid, $size));
		self::reverse( $list );
	}
	
}

class UnmodifiableCollection implements Collection {
	protected $c;

	public function __construct( Collection $c) {
		if (is_null($c))
			throw new NullPointerException();
		$this->c = $c;
	}
	public function size() 					{ return $this->c->size(); }
	public function isEmpty()				{ return $this->c->isEmpty(); }
	public function contains( Object $o )	{ return $this->c->contains($o); }
	public function containsAll(Collection $c)	{ return $this->c->containsAll($c); }
	public function toArray()				{ return $this->c->toArray(); }
	public function toString()				{ return $this->c->toString(); }
	public function equals( Object $o ) 	{ return $this->c->equals($o); }
	public function hashCode()				{ return $this->c->hashCode(); }
	
	public function iterator()				{ return new UnmodifiableCollection_Iterator( $this->iterator() ); }
	
	public function add( Object $o )			{ throw new UnsupportedOperationException(); }
	public function remove( Object $o ) 		{ throw new UnsupportedOperationException(); }
	public function addAll( Collection $c )		{ throw new UnsupportedOperationException(); }
	public function removeAll( Collection $c ) 	{ throw new UnsupportedOperationException(); }
	public function retainAll( Collection $c ) 	{ throw new UnsupportedOperationException(); }
	public function clear() 					{ throw new UnsupportedOperationException(); }	
}

class UnmodifiableCollection_Iterator implements CollectionIterator {
	private $i;
	public function __construct( CollectionIterator $itr ) {
		$this->i = $itr;
	}
	public function hasNext() 	{ return $this->i->hasNext(); }
	public function getNext() 	{ return $this->i->getNext(); }
	public function remove() 	{ throw new UnsupportedOperationException(); }	
	
	public function current()	{ return $this->i->current(); }
	public function key()		{ return $this->i->key(); }
	public function next()		{ return $this->i->next(); }
	public function valid()		{ return $this->i->valid(); }
	public function rewind()	{ return $this->i->rewind(); }
}

class UnmodifiableSet extends UnmodifiableCollection implements Set {
	public function __construct( Set $s ) 	{ parent::__construct($s); }
	
	public function equals( Object $o ) 	{ return $this->c->equals($o); }
	public function hashCode()				{ return $this->c->hashCode(); }
}

class UnmodifiableSortedSet extends UnmodifiableSet implements SortedSet {
	private $ss;
	public function __construct( SortedSet $s ) { parent::__construct($s); $this->ss = $s; }
	
	public function comparator() 				{ return $this->ss->comparator(); }
	
	public function subSet( Object $fromElement, Object $toElement ) {
		return new UnmodifiableSortedSet( $this->ss->subSet( $fromElement, $toElement) );
	}
	
	public function headSet( Object $toElement ) {
		return new UnmodifiableSortedSet( $this->ss->headSet( $toElement ) );
	}
	
	public function tailSet( Object $fromElement ) {
		return new UnmodifiableSortedSet( $this->ss->tailSet( $fromElement ) );
	}
	
	public function first()		{ return $this->ss->first(); }
	public function last()		{ return $this->ss->last(); }
	
}

class UnmodifiableList extends UnmodifiableCollection implements Llist {
	protected $l;
	public function __construct( LList $list ) {
		parent::__construt( $list );
		$this->l = $list;
	}
	
	public function equals( Object $o ) 		{ return $this->l->equals( $o ); }
	public function hashCode()					{ return $this->l->hashCode(); }
	
	public function get( $index ) 				{ return $this->l->get( $index ); }
	
	public function set( $index, Object $element ) 		{ throw new UnsupportedOperationException(); }
	public function addAt( $index, Object $element ) 	{ throw new UnsupportedOperationException(); }
	public function addAllAt( $index, Collection $c ) 	{ throw new UnsupportedOperationException(); }
	public function removeAt( $index ) 					{ throw new UnsupportedOperationException(); }
	
	public function indexOf( Object $o )		{ return $this->l->indexOf( $o ); }
	public function lastIndexOf( Object $o ) 	{ return $this->l->lastIndexOf( $o ); }
	
	public function listIterator()	{
		return $this->listIteratorAt(0);
	}
	
	public function listIteratorAt( $index ) {
		return new UnmodifiableList_ListIterator( $this->l->listIteratorAt( $index ) );
	}
	
	public function subList( $fromIndex, $toIndex ) {
		return new UnModifiableList( $this->l->subList( $fromIndex, $toIndex ));
	}
}

class UnmodifiableList_ListIterator implements CollectionIterator {
	private $i;
	
	public function __construct( CollectionIterator $itr ) {
		$this->i = $itr;
	}
	
	public function hasNext() 		{ return $this->i->hasNext(); }
	public function getNext() 		{ return $this->i->getNext(); }
	public function hasPrevious() 	{ return $this->i->hasPrevious(); }
	public function getPrevious() 	{ return $this->i->getPrevious(); }
	public function nextIndex() 	{ return $this->i->nextIndex(); }
	public function previousIndex() { return $this->i->previousIndex(); }
	
	public function remove()		{ throw new UnsupportedOperationException(); }
	public function set( Object $o)	{ throw new UnsupportedOperationException(); }
	public function add( Object $o)	{ throw new UnsupportedOperationException(); }
	
	public function current()		{ return $this->i->current(); }
	public function key()			{ return $this->i->key(); }
	public function next()			{ return $this->i->next(); }
	public function valid()			{ return $this->i->valid(); }
	public function rewind()		{ return $this->i->rewind(); } 
}	

class UnmodifiableRandomAccessList extends UnmodifiableList implements RandomAccess {
	public function __construct( Llist $list ) { parent::__construct( $list ); }
	
	public function subList( $fromIndex, $toIndex) {
		return new UnmodifiableRandomAccessList( $this->l->subList( $fromIndex, $toIndex ));
	}
}

class UnmodifiableMap implements Map {
	protected $m;
	
	public function __construct( Map $m ) {
		if (is_null( $m ))
			throw new NullPointerException();
			
		$this->m = $m;
	}
	
	public function size()							{ return $this->m->size(); }
	public function isEmpty()						{ return $this->m->isEmpty(); }
	public function containsKey( Object $key ) 		{ return $this->m->containsKey( $key ); }
	public function containsValue( Object $val ) 	{ return $this->m->containsValue( $val ); }
	public function get( Object $key )				{ return $this->m->get( $key ); }
	
	public function put( Object $key, Object $value )	{ throw new UnsupportedOperationException(); }
	public function remove( Object $key ) 				{ throw new UnsupportedOperationException(); }
	public function putAll( Map $t )					{ throw new UnsupportedOperationException(); }
	public function clear()								{ throw new UnsupportedOperationException(); }
	
	private $keySet = null;
	private $entrySet = null;
	private $values = null;
	
	public function keySet() {
		if (is_null($this->keySet))
			$this->keySet = new UnmodifiableSet( $this->m->keySet() );
		return $this->keySet;
	}
	
	public function entrySet() {
		if (is_null( $this->entrySet ))
			$this->entrySet = new UnmodifiableEntrySet( $this->m->entrySet() );
		return $this->entrySet;
	}
	public function values() {
		if (is_null( $this->values ))
			$this->values = new UnmodifiableCollection( $this->m->values() );
		return $this->values;
	}
	
	public function equals( Object $o )			{ return $this->m->equals( $o ); }
	public function hashCode()					{ return $this->m->hashCode(); }
	public function toString()					{ return $this->m->toString(); }
}

class UnmodifiableEntrySet extends UnmodifiableSet {
	public function __construct( Set $s ) {
		parent::__construct( $s );
	}
	
	public function iterator() {
		return new UnmodifiableEntrySet_Iterator( $this->c->iterator() );
	}
	
	public function toArray() {
		$a = $this->c->toArray();
		for ($i = 0; $i < $this->c->size(); $i++) {
			$a[i] = new UnmodifiableEntry( $a[$i] );
		}
		return $a;
	}
	/**
	 * This method is overridden to protect the backing set against
	 * an object with a nefarious equals function that senses
	 * that the equality-candidate is Map.Entry and calls its
	 * setValue method.
	 */ 
	public function contains( Object $o ) {
		if (!($o instanceof MapEntry))
			return false;
		return $this->c->contains( new UnmodifiableEntry( $o ));
	}
	
	public function containsAll( Collection $c ) {
		$e = $c->iterator();
		while ($e->hasNext()) 	
			if (! $this->contains( $e->getNext() ))
				return false;
		return true;
	}
	
	public function equals( Object $o ) {
		if ($o === $this )
			return true;
			
		if (!($o instanceof Set))
			return false;
			
		$s = $o;
		if ($s->size() != $this->c->size())
			return false;
		return $this->containsAll( $s );
	}
}

class UnmodifiableEntry implements MapEntry {
	private $e;
	
	public function __construct( MapEntry $e) {
		$this->e = $e;
	}
	
	public function getKey()	{ return $this->e->getKey(); }
	public function getValue()	{ return $this->e->getValue(); }
	
	public function setValue( Object $o ) 	{ throw new UnsupportedOperationException(); }
	public function hashCode()	{ return $this->e->hashCode(); }
	public function equals( Object $o ) {
		if (!( $o instanceof MapEntry))
			return false;
		$t = $o;
		return Collections::eq( $this->e->getKey(), $o->getKey() ) and Collections::eq( $this->e->getValue(), $o->getValue() );
	}
	
	public function toString()	{ return $this->e->toString(); }
}

class UnmodifiableSortedMap extends UnmodifiableMap implements SortedMap {
	private $sm;
	
	public function __construct( SortedMap $m ) {
		parent::__construct( $m );
		$this->sm = $m;
	}
	public function comparator()	{ return $this->sm->comparator(); }
	public function subMap( Object $fromKey, Object $toKey ) {
		return new UnmodifiableSortedMap( $this->sm->subMap( $fromKey, $toKey ) );
	}
	public function headMap( Object $toKey ) {
		return new UnmodifiableSortedMap( $this->sm->headMap( $toKey ));
	}
	public function tailMap( Object $fromKey ) {
		return new UnmodifiableSortedMap( $this->sm->tailMap( $fromKey ));
	}
	
	public function firstKey() 		{ return $this->sm->firstKey(); }
	public function lastKey()		{ return $this->sm->lastKey(); }
}

class EmptySet extends AbstractSet {
	public function iterator() {
		return new EmptySet_Iterator();
	}
	
	public function size() {
		return 0;
	}
	public function contains( Object $o ) {
		return false;
	}
}

class EmptySet_Iterator implements CollectionIterator {
	
	public function hasNext() {
		return false;
	}
	public function getNext() {
		throw new NoSuchElementException();
	}
	public function remove() {
		throw new UnsupportedOperationException();
	}
	
	public function current()		{ throw new NoSuchElementException(); }
	public function key()			{ throw new UnsupportedOperationException(); }
	public function next()			{  }
	public function valid()			{ return false; }
	public function rewind()		{  } 
	
}

class EmptyList extends AbstractList implements RandomAccess {
	public function size() {
		return 0;
	}
	public function contains( Object $o ) {
		return false;
	}
	public function get( $index ) {
		throw new IndexOutOfBoundsException("Index: " . $index );
	}
}

class EmptyMap extends AbstractMap {
	public function size() {
		return 0;
	}
	public function isEmpty() {
		return true;
	}
	public function containsKey( Object $key ) {
		return false;
	}
	public function containsValue( Object $value ) {
		return false;
	}
	public function get( Object $key ) {
		return null;
	}
	public function keySet() {
		return new EmptySet();
	}
	public function entrySet() {
		return new EmptySet();
	}
	public function values() {
		return new EmptySet();
	}
	
	public function equals( Object $o ) {
		return ($o instanceof Map) and ($o->size() == 0);
	}
	public function hashCode() {
		return 0;
	}
}

?>